package me.timlong;

import java.util.*;

/**
 * 140. Word Break II
 * @author Administrator
 * 对牛客网的评判标准真是无语，为什么一定要按固定顺序输出？这点还是leetcode做的好。
 * 附上leetcode地址：
 * <a href="https://leetcode.com/problems/word-break-ii/" target="_blank">
 *     https://leetcode.com/problems/word-break-ii/#/description
 *
 */
public class StringToSentence {

    /*
     * 动态规划思想，用map把已经求得的结果存起来，避免重复劳动
     */
    public ArrayList<String> wordBreak(String s, Set<String> wordDict) {
        return DFS(s, wordDict, new HashMap<String, ArrayList<String>>());
    }

    private ArrayList<String> DFS(String s, Set<String> wordDict, HashMap<String, ArrayList<String>> map) {
        if (map.containsKey(s))
            return map.get(s);
        ArrayList<String> res = new ArrayList<String>();
        if (s.length() == 0){
            res.add("");
            return res;
        }
        for (String subStr : wordDict) {
            if (s.startsWith(subStr)) {
                for (String str : DFS(s.substring(subStr.length()), wordDict, map)) {
                    res.add(subStr + (str == "" ? "" : " ")+ str);
                }
            }
        }
        map.put( s, res);
        return res;
    }

    /**
     * 动态规划思想，对已经计算过的进行保留
     * 用一个ArrayList<String> 来存储计算过的子字符串的word break结果，减少重复计算
     *
     *
     */
    public ArrayList<String> wordBreaks(String s, Set<String> wordDict) {
        return dfs(s, wordDict, new HashMap<String, ArrayList<String>>());
    }

    private ArrayList<String> dfs(String s, Set<String> wordDict, HashMap<String, ArrayList<String>> map){
        if(map.containsKey(s))
            return map.get(s);

        ArrayList<String> result = new ArrayList<>();
        if(s.equals(""))
            result.add("");

        for (String word: wordDict) {
            if(s.startsWith(word)){
                ArrayList<String> temRes = dfs(s.substring(word.length()), wordDict, map);
                for (String elem : temRes) {
                    result.add(word + (elem.equals("") ? "" : " " + elem));
                }
            }
        }
        map.put(s, result);
        return result;
    }

    public static void main(String[] args) {
        String[] dict = {"cat", "cats", "and", "sand", "dog"};
        String s = "catsanddog";

        Set<String> word_dict = new HashSet<String>(Arrays.asList(dict));
        for(String elem : new StringToSentence().dfs(s, word_dict, new HashMap<>())){
            System.out.println(elem + ", ");
        }
    }
}
